//
// Created by gyc on 2020/8/5.
//
#define NULL nullptr

#include <iostream>

#include "../../common.h"

class Solution {
public:
    TreeNode *mergeTrees(TreeNode *root1, TreeNode *root2) {

        if (root1 == nullptr) {
            return root2;
        }
        if (root2 == nullptr) {
            return root1;
        }

        queue<TreeNode *> q1{};
        queue<TreeNode *> q2{};

        q1.emplace(root1);
        q2.emplace(root2);

        while (!q1.empty() && !q2.empty()) {
            TreeNode *p1 = q1.front();
            q1.pop();
            TreeNode *p2 = q2.front();
            q2.pop();
            p1->val += p2->val;
            if (p1->left == nullptr) {
                p1->left = p2->left;
            } else if (p2->left != nullptr) {
                q1.emplace(p1->left);
                q2.emplace(p2->left);
            }
            if (p1->right == nullptr) {
                p1->right = p2->right;
            } else if(p2->right != nullptr) {
                q1.emplace(p1->right);
                q2.emplace(p2->right);
            }
        }
        return root1;
    }
};

int main() {

    TreeNode t1(1), t2(3), t3(2), t4(5);
    t1.left = &t2;
    // t1.right = &t3;
    t2.left = &t4;

    TreeNode tt1(12), tt2(11), tt3(13), tt4(14), tt5(17);
    tt1.left = &tt2;
    tt1.right = &tt3;
    tt3.left = &tt4;
    tt3.right = &tt5;

    TreeNode *r = Solution().mergeTrees(&t1, &tt1);
    cout << r->val << endl;
}
